/*
 * @lc app=leetcode id=213 lang=cpp
 *
 * [213] House Robber II
 */
class Solution {
public:
    int rob(vector<int>& nums) {

        int len = nums.size();
        if (len < 1) {
            return 0;
        } else if (len < 2) {
            return nums[0];
        }

        return std::max(rob(nums, 0, len-1), rob(nums, 1, len-1));
    }

    int rob(vector<int>& nums, int idx, int len) {
        
        vector<int> memo(len+1, 0);
        memo[0] = 0;
        memo[1] = nums[idx];

        for (int i=2; i<=len; i++) {
            if (memo[i-2] + nums[i+idx-1] > memo[i-1]) {
                memo[i] = memo[i-2] + nums[i+idx-1];
            } else {
                memo[i] = memo[i-1];
            }
        }

        return memo[len];
    }
};

